package com.lft.ten_commonly_used_algorithms03.dynamic_programming;

import java.util.Arrays;
import java.util.Stack;

/**
 * 动态规划——背包问题
 */
public class DynamicProgramming {
	public static void main(String[] args) {
		// 物品的重量
		int[] weightOfCommodity = {1, 4, 3, 2, 5};
		// 物品的价值
		int[] valueOfCommodity = {1500, 3000, 2000, 1000, 2500};
		// 背包的承重量
		int carryingCapacity = 4;
		knapsackProblem(weightOfCommodity, valueOfCommodity, carryingCapacity);
	}
	
	public static void knapsackProblem(int[] weightOfCommodity, int[] valueOfCommodity, int carryingCapacity) {
		// 物品的个数
		int number = valueOfCommodity.length;
		// valueOfKnapsack[i][j] 表示在前 i 个物品中能够装入容量为 j 的背包中的最大价值。
		int[][] valueOfKnapsack = new int[number + 1][carryingCapacity + 1];
		// 记录商品的放入情况
		int[][] path = new int[number + 1][carryingCapacity + 1];
		// 初始化第一行第一列为0。可以不处理，默认就是0.
		for (int i = 0; i < valueOfKnapsack.length; i++) {
			// 将第一列设置为 0
			valueOfKnapsack[i][0] = 0;
		}
		for (int j = 0; j < valueOfKnapsack[0].length; j++) {
			// 将第一行设置为 0
			valueOfKnapsack[0][j] = 0;
		}
		
		// 根据前面得到的公式来动态规划处理，不处理第一行。遍历当放入第 i 号商品时。
		for (int noOfCommodity = 1; noOfCommodity < valueOfKnapsack.length; noOfCommodity++) {
			// 处理行。不处理第一行。遍历背包容量为 j
			for (int capacityOfKnapsack = 1; capacityOfKnapsack < valueOfKnapsack[0].length; capacityOfKnapsack++) {
				// 处理列。不处理第一列。
				// 当 noOfCommodity 个商品的重量（在 weightOfCommodity 数组中索引应该是 noOfCommodity - 1） > 此时背包的容量 capacityOfKnapsack 时。
				if (weightOfCommodity[noOfCommodity - 1] > capacityOfKnapsack) {
					// 背包中，第 noOfCommodity 个商品在背包容量为 capacityOfKnapsack 时的价值为
					// 就是第 noOfCommodity-1 个商品在背包容量为 capacityOfKnapsack 时的价值。
					valueOfKnapsack[noOfCommodity][capacityOfKnapsack] = valueOfKnapsack[noOfCommodity - 1][capacityOfKnapsack];
				} else {
					// 当 noOfCommodity 个商品的重量（在 weightOfCommodity 数组中索引应该是 noOfCommodity - 1） < 此时背包的容量 capacityOfKnapsack 时。
					// 程序中 noOfCommodity 从1开始，因此要调整。
					// valueOfKnapsack[noOfCommodity][capacityOfKnapsack] = Math.max(valueOfKnapsack[noOfCommodity -
					// 1][capacityOfKnapsack], valueOfCommodity[noOfCommodity - 1] + valueOfKnapsack[noOfCommodity - 1][capacityOfKnapsack
					// - weightOfCommodity[noOfCommodity - 1]]);
					
					// 为了记录商品存放到背包的情况。不能直接用上面的公式，而是用if-else来体现公式。
					// ① valueOfKnapsack[noOfCommodity - 1][capacityOfKnapsack]：同一背包容量，前一个物品的价值。
					// ② valueOfCommodity[noOfCommodity - 1]：当前物品的价值
					// ③ valueOfKnapsack[noOfCommodity - 1][capacityOfKnapsack - weightOfCommodity[noOfCommodity - 1]]：前一个物品，在剩余背包容量时的最大值。
					if (valueOfKnapsack[noOfCommodity - 1][capacityOfKnapsack] < valueOfCommodity[noOfCommodity - 1] + valueOfKnapsack[noOfCommodity - 1][capacityOfKnapsack - weightOfCommodity[noOfCommodity - 1]]) {
						// 将 当前物品的价值 设置为 当前物品的价值 + 前一个物品在剩余背包容量时的最大值。
						valueOfKnapsack[noOfCommodity][capacityOfKnapsack] =
								valueOfCommodity[noOfCommodity - 1] + valueOfKnapsack[noOfCommodity - 1][capacityOfKnapsack - weightOfCommodity[noOfCommodity - 1]];
						// 记录路径。
						path[noOfCommodity][capacityOfKnapsack] = 1;
					} else {
						// 就将同一背包容量下前一物品的价值赋值给当前物品的价值。
						valueOfKnapsack[noOfCommodity][capacityOfKnapsack] = valueOfKnapsack[noOfCommodity - 1][capacityOfKnapsack];
					}
				}
			}
		}
		
		// 输出一下V 看一下。
		for (int[] ints : valueOfKnapsack) {
			System.out.println(Arrays.toString(ints));
		}
		
		// 输出存放方法。从后往前找。每找一次，背包的容量减掉找出来的商品的容量。
		// 从后往前找的。
		// 行的最大下标。行表示是第几个商品。
		int i = path.length - 1;
		// 列的最大下标。列表示背包容量。
		int j = path[i].length - 1;
		// 找到了放在栈中。
		Stack<Integer> stack = new Stack<>();
		// 从path 数组最后开始找。
		while (i > 0 && j > 0) {
			if (path[i][j] == 1) {
				stack.push(i);
				// 背包的承重量 = 现在的背包的承重量 - 放入商品的重量。
				j -= weightOfCommodity[i - 1];
			}
			i--;
		}
		// 再从栈中从前往后顺序取出。
		while (!stack.isEmpty()) {
			System.out.printf("第 %d 个商品放入到背包\n", stack.pop());
		}
	}
}